<?php
/**
 * @title 32. 最长有效括号 - 动态规划
 * @author start2004
 */

class Solution {

    /**
     * @param String $s
     * @return Integer
     */
    function longestValidParentheses($s) {
        /**
         * @since 2020-07-14 长度
         */
        $len = strlen($s);

        /**
         * @since 2020-07-14 最长有效括号长度
         */
        $maxLen = 0;

        /**
         * @since 2020-07-14 有效括号长度数组
         */
        $dpArray = array_fill(-1, $len+1, 0);

        /**
         * @since 2020-07-14 循环
         */
        for($i=0; $i<$len; $i++){
            /**
             * @since 2020-07-14 找到与其匹配的`(`
             */
            if($s[$i] == ")"){
                if($i >= 1){
                    /**
                     * @since 2020-07-14 dp(i)=dp(i−2)+2
                     */
                    if($s[$i-1] == "(") {
                        $dpArray[$i] = $dpArray[$i-2] + 2;
                        $maxLen = max($maxLen, $dpArray[$i]);
                    } else {
                        /**
                         * @since 2020-07-14 s[i-1] = )
                         *
                         * dp(i)=dp(i−1)+2+dp(i−dp(i−1)−2)
                         *
                         * 对应的左指针
                         */
                        $left = $i-$dpArray[$i-1]-1;
                        if($left >= 0){
                            if($s[$left] == "("){
                                /**
                                 * @since 2020-07-14 左括号匹配成功
                                 */
                                $dpArray[$i] = $dpArray[$i-1] + $dpArray[$i-$dpArray[$i-1]-2] + 2;
                                $maxLen = max($maxLen, $dpArray[$i]);
                            } else {}
                        }
                    }
                } else {
                    /**
                     * @since 2020-07-14 `)`开头, 无效括号
                     */
                }
            } else {
                /**
                 * @since 2020-07-14 `(`不处理
                 */
            }
        }

        /**
         * @return
         */
        // return $dpArray;
        return $maxLen;
        // return max($dpArray);
    }
}


/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.04_2.php
 */
$datas = [
    // "",
    "(()))())(",
    // ")()())",
    // "(()(()",
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->longestValidParentheses($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
